package com.mlh.heap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author 缪林辉
 * @date 2024/3/24 23:16
 * @DESCRIPTION
 */
// 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
// 示例 1:
// 输入: nums = [1,1,1,2,2,3], k = 2
// 输出: [1,2]

/*Comparator接口说明:
 * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
 * 对于队列：排在前面意味着往队头靠
 * 是大根堆还是小根堆 取决你怎么重写comparator
 * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
 * 从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
 * */
public class 前K个高频元素 {

    //解法1：基于小顶堆实现
    public int[] method1(int[] nums, int k) {
        //key为数组元素值,val为对应出现次数
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
        //我刚开始想用map，map在这里没意义，你又不用通过key来干嘛，直接用数组记录两个数字就好
        //(pair1, pair2)->pair1[1]-pair2[1]：出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> queue=new PriorityQueue<>((pair1, pair2)->pair1[1]-pair2[1]);
        //小顶堆只需要维持k个元素有序
        for(Map.Entry<Integer,Integer>entry:map.entrySet()){
            if(queue.size()>=k&&entry.getValue()>queue.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                queue.poll();
                queue.add(new int[]{entry.getKey(),entry.getValue()});
            }else if(queue.size()<k){//小顶堆元素个数小于k个时直接加
                queue.add(new int[]{entry.getKey(),entry.getValue()});
            }
        }
        int[]res=new int[k];
        //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
        //因此数组逆序排序(不过无所谓 题目没有说要按照频率来输出答案)
        for (int i = k-1; i >=0; i--) {
            res[i]=queue.poll()[0];
        }
        return res;
    }

    public int[] practice(int[] nums, int k) {
        HashMap<Integer,Integer>map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        PriorityQueue<int[]>queue=new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            if(queue.size()<k){
                queue.offer(new int[]{entry.getKey(), entry.getValue()});
            }else{
                if(entry.getValue()>queue.peek()[1]){
                    queue.poll();
                    queue.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[]res=new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=queue.poll()[0];
        }
        return res;
    }

    public int[] practice2(int[] nums, int k) {
        Map<Integer,Integer>map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.getOrDefault(nums[i],0)==0){
                map.put(nums[i],1);
            }else{
                map.merge(nums[i],1,Integer::sum);
            }
        }
        PriorityQueue<int[]>heap=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            if(heap.size()<k){
                heap.add(new int[]{e.getKey(),e.getValue()});
            }else{
                if(heap.peek()[0]<e.getValue()){
                    heap.poll();
                    heap.add(new int[]{e.getKey(),e.getValue()});
                }
            }
        }
        int[]res=new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=heap.poll()[0];
        }
        return res;
    }

    //学习一下别人的代码
    // public int[] topKFrequent(int[] nums, int k) {
    //         int[] ans = new int[k];
    //         Map<Integer, Integer> map = new HashMap();
    //
    //         for(int i = 0; i < nums.length; i++){
    //             map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    //         }
    //
    //         PriorityQueue<Integer> pq = new PriorityQueue(new Comparator<Integer>(){
    //             public int compare(Integer n1, Integer n2){
    //                 return map.get(n2) - map.get(n1);
    //             }
    //         });
    //
    //         for(Integer key : map.keySet()){
    //             pq.offer(key);
    //         }
    //
    //         for(int i = 0; i < k; i++){
    //             ans[i] = pq.poll();
    //         }
    //
    //         return ans;
    //     }
}
